#include <stdio.h>
#include <omp.h>
#include <stdlib.h>
#include <time.h>
#include "fun_group.h"

/**
 * 函数名：parallel_BubbleSort
 * 功能：使用OpenMP实现并行冒泡排序
 */

void merge(int *a, int *b, int left, int mid, int right)
{
    int i, left_end, count, tmp_pos;
    left_end = mid - 1;
    tmp_pos = left;
    count = right - left + 1;

    // Main merge
    while ((left <= left_end) && (mid <= right))
    {
        if (a[left] <= a[mid])
        {
            b[tmp_pos] = a[left];
            tmp_pos++;
            left++;
        }
        else
        {
            b[tmp_pos] = a[mid];
            tmp_pos++;
            mid++;
        }
    }

    // Copy remainder of left
    while (left <= left_end)
    {
        b[tmp_pos] = a[left];
        left++;
        tmp_pos++;
    }

    // Copy remainder of right
    while (mid <= right)
    {
        b[tmp_pos] = a[mid];
        mid++;
        tmp_pos++;
    }

    // Copy temp array back to original
    for (i = 0; i < count; ++i)
    {
        a[right] = b[right];
        right--;
    }
}

void bubbleSort(int *a, int left, int right)
{
    int i, j;
    for (i = left; i < right; i++)

        for (j = left; j < right - i; j++)
            if (a[j] > a[j + 1])
                swap(&a[j], &a[j + 1]);
}

void split_bubblesort(int subarrayLength, int proc_num, int DataSize, int *data1, int *data2)
{
#pragma omp parallel
    {
        int tid = omp_get_thread_num();
        int l = tid * subarrayLength;
        int r = l + subarrayLength - 1;
        if (tid < proc_num - 1) // All but the last thread
            bubbleSort(data1, l, r);
        else // Last thread
            bubbleSort(data2, l, DataSize - 1);
    }
}

int main()
{
    double parallel_start_time, parallel_end_time, serial_end_time, serial_start_time;

    // 产生排序数据
    int size_list[11] = {1e3, 1e4, 2e4, 3e4, 4e4, 5e4, 6e4, 7e4, 8e4, 1e5};
    int DataSize = 1e3;
    int proc_num = 12;
    for (int i = 0; i < 11; i++)
    {
        for (int j = 2; j < 13; j++)
        {
            int DataSize = size_list[i]; // set data size
            int proc_num = j; // set the number of processes
            omp_set_num_threads(proc_num);
            const int SIZE = DataSize * sizeof(int); // size for the array
            int *data1 = (int *)malloc(SIZE);
            int *data2 = (int *)malloc(SIZE);
            int *dataCopy = (int *)malloc(SIZE);
            CreateData(data1, DataSize);
            for (int i = 0; i < DataSize; ++i)
                dataCopy[i] = data1[i];

            // 并行冒泡排序
            parallel_start_time = omp_get_wtime();
            int subarrayLength = DataSize / proc_num;
            split_bubblesort(subarrayLength, proc_num, DataSize, data1, data2);
            for (int i = 1; i <= proc_num - 2; i++)
            { // All but the last subarray
                int middle = i * subarrayLength;
                merge(data1, data2, 0, middle, middle + subarrayLength - 1);
            }
            merge(data1, data2, 0, (proc_num - 1) * subarrayLength, DataSize - 1); // Last subarray
            parallel_end_time = omp_get_wtime();

            for (int i = 0; i < 100; i++)
            {
                printf("%d ", data1[i]);
            }
            printf("\n");

            // 串行冒泡排序
            serial_start_time = omp_get_wtime();
            serial_BubbleSort(dataCopy, DataSize);
            serial_end_time = omp_get_wtime();

            char sort_name[] = "opm_bubblesort";
            char filepath[] = "result_bubble_opm.txt";
            put_time_info(filepath, sort_name, DataSize, proc_num, parallel_start_time, parallel_end_time, serial_start_time, serial_end_time);
        }
    }

    return 0;
}
